package demo3;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Administrator
 * Date: 2023-07-07
 * Time: 16:09
 */
public class MySingleList {
    class ListNode{
        private int val;
        private ListNode next;

        public ListNode(int val){
            this.val = val;
        }
    }
    public ListNode head;


    public void createList(){
        MySingleList.ListNode node1 = new MySingleList.ListNode(10);
        MySingleList.ListNode node2 = new MySingleList.ListNode(15);
        MySingleList.ListNode node3 = new MySingleList.ListNode(18);
        MySingleList.ListNode node4 = new MySingleList.ListNode(21);
        MySingleList.ListNode node5 = new MySingleList.ListNode(25);


        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;

        this.head = node1;
    }


    //遍历单链表
    public void show(){
        ListNode cur = head;
       while (cur != null){
           System.out.println(cur.val+" ");
           cur = cur.next;
       }
    }


    //求链表长度
    public int size(){
        int count = 0;
        ListNode cur = head;
        while (cur != null){
            cur = cur.next;
            count++;
        }
        return count;
    }

    //判断链表是否包含key值
    public boolean contains(int key){
        ListNode cur = head;
        while (cur != null){
            if(cur.val == key){
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    //头插法
    public void addFirst(int data){
        ListNode node = new ListNode(data);
        if(head == null){
            head = node;
        }
        node.next = head;
        head = node;

    }

    //尾插法
    public void addLast(int data){
        ListNode node = new ListNode(data);
        if(head == null){
            head = node;
            return;
        }
        ListNode cur = head;
        while (cur.next != null){
            cur = cur.next;
        }
        cur.next = node;
    }

    //找到index-1位置的节点
    private ListNode findIndex(int index){
        ListNode cur = head;
        while (index -1 != 0){
            cur = cur.next;
            index--;
        }
        return cur;
    }
    //在index位置下插入值
    public void addIndex(int index,int data){
        ListNode node = new ListNode(data);
        int len = size();
        if(index < 0 || index > len){
            throw new indexOutOfBounds("index下标不合法");
        }
        if(index == 0){
           addFirst(data);
           return;
        }
        if(index == len){
            addLast(data);
            return;
        }
        ListNode cur = findIndex(index);
        node.next = cur.next;
        cur.next = node;
    }

    private ListNode searchPrev(int key){
        ListNode prev = head;
        while (prev.next != null){
            if(prev.next.val == key){
                return prev;
            }else {
                prev = prev.next;
            }
        }
        return null;
    }
    //删除第一次出现关键字key的节点
    public void remove(int key){
        if(head == null){
            return;
        }
        if(head.val == key){
            head = head.next;
        }
        ListNode prev = searchPrev(key);
        if(prev == null){
            System.out.println("没有你要删除的数据");
            return;
        }
        ListNode del = prev.next;
        prev.next = del.next;

    }

    //删除所有值为key的节点
    public void removeAllkey(int key){
        if(head == null){
            return;
        }
        ListNode prev = head;
        ListNode cur = head.next;
        while (cur != null){
            if(cur.val == key){
                prev.next = cur.next;
                cur = cur.next;
            }else{
                prev = cur;
                cur = cur.next;
            }
        }
        if(head.val == key){
            head = head.next;
        }

    }

    //清空链表

    public void clear(){

    }

}
